/*
 * @Author: zxc
 * @Date: 2020-08-13 19:45:43
 * @LastEditTime: 2020-08-14 21:22:14
 * @LastEditors: zxc
 * @Description: bfs 广度优先搜索
 */
import Queue from "../test/Queue/queue";

const Colors = {
  WHITE: 0,
  GREY: 1,
  BLACK: 2,
};

const initializeColor = (vertices) => {
  const color = {};
  for (let i = 0; i < vertices.length; i++) {
    color[vertices[i]] = Colors.WHITE;
  }
  return color;
};

/**
 * @Author: zxc
 * @Date: 2020-08-13 19:58:11
 * @func: 这里因为书里的讲法我觉得太他喵的蠢了，我进行单独的解释
 * 首先，接收一个图，以及图的一个起步点，还有一个回调函数
 * 方法的流程是这样的：
 * 1. 首先，我们获取图的顶点数据和边的字典
 * 2. 将所有的节点的色度都置为白色
 * 3. 将首节点入队列
 * 4. 判断队队是否为空队列，如果不为空队列，我们将队列底元素抛出，并保存起来
 * 5. 通过取出的这个元素，我们去字典里，根据这个key去寻找相应的values
 * 6. 将色标组里的这个节点的色度置为灰色度
 * 7. 循环遍历这个key对应的values，如果遍历的值在color中对应的色度为白色度，那就就将这个值入队列
 * 8. 遍历完了，将这个值在color中的色度置黑，表示已经对它进行了“调教”
 * 9. 然后继续重复步骤4-8
 */
export const breadthFirstSearch = (graph, startVertex, callback) => {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = initializeColor(vertices);
  const queue = new Queue();

  queue.enqueue(startVertex);

  while (!queue.isEmpty()) {
    const u = queue.dequeue();
    const neighbors = adjList.get(u);
    color[u] = Colors.GREY;
    for (let i = 0; i < neighbors.length; i++) {
      const w = neighbors[i];
      if (color[w] === Colors.WHITE) {
        color[w] = Colors.GREY;
        queue.enqueue(w);
      }
    }
    color[u] = Colors.BLACK;
    if (callback) {
      callback(u);
    }
  }
};


/**
 * @Author: zxc
 * @Date: 2020-08-13 20:25:51
 * @func: bsf最短路径
 * 它是上面的bfs算法的一种优化和升级，具体看不一样的地方 
 * 首先，它新增了
 *     1. distances:用来存放startvertex到每一个节点的最短路径值
 *     2. predecessors:用来存放每个节点的上属节点（回溯节点）
 * 遍历图的节点数组，将每个值作为distances和predecessors的key，并为其赋初始值，distances为0，predecessors为null
 * 后面流程和BSF大致一样，唯一不同的点就是它会在找到white时
 * 将对应的distances和predecessors进行赋值
 * 赋值依据：
 *  1. distances是根据寻找到当前所对就的key之前的出队列的值的key对应的distances里的value+1
 *  2. predecessors是将出队列的key作为当前的key的value
 */
export const BFS = (graph, startVertex) => {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = initializeColor(vertices);
  const queue = new Queue();
  const distances = {};
  const predecessors = {};
  queue.enqueue(startVertex);
  for (let i = 0; i < vertices.length; i++) {
    distances[vertices[i]] = 0;
    predecessors[vertices[i]] = null;
  }
  while (!queue.isEmpty()) {
    const u = queue.dequeue();
    const neighbors = adjList.get(u);
    color[u] = Colors.GREY;
    for (let i = 0; i < neighbors.length; i++) {
      const w = neighbors[i];
      if (color[w] === Colors.WHITE) {
        color[w] = Colors.GREY;
        distances[w] = distances[u] + 1;
        predecessors[w] = u;
        queue.enqueue(w);
      }
    }
    color[u] = Colors.BLACK;
  }
  return {
    distances,
    predecessors
  };
};

//from A to all other vertices
/**
 * @Author: zxc
 * @Date: 2020-08-13 20:32:58
 * @func: 这是一个回溯出某个顶点到其它顶点路径的方法
 */
// const fromVertex = myVertices[0];

// for (let i = 1; i < myVertices.length; i++) {
//   const toVertex = myVertices[i];
//   const path = new Stack();
//   for (let v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
//     path.push(v);
//   }
//   path.push(fromVertex);
//   let s = path.pop();
//   while (!path.isEmpty()) {
//     s += ' - ' + path.pop();
//   }
//   console.log(s);
// }